package 每日一题;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-18
 **/

public class No476数字的补数 {

    /**
     * 对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
     * 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。
     * 给你一个整数 num ，输出它的补数。
     *
     * 示例 1：
     * 输入：num = 5
     * 输出：2
     * 解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
     * 示例 2：
     * 输入：num = 1
     * 输出：0
     * 解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
     *  
     * 提示：
     * 1 <= num < 23^1
     */

    // 方法一 逐位
    public int findComplement(int num) {

        if (num == 0) {
            return 1;
        }

        int n = 1;
        // 找到最高位bit
        for (int i = 0; i <= 31; i++) {
            if ((num - n) <= 0) {
                // 找到了最高位
                n = i;
                break;
            }
            n <<= 1;
        }

        // 最高位是n
        int nn = 1;
        int ans = 0; //一位一位更改
        for (int i = 0; i < n; i++) {
            if ((nn & num) == 0) {
                // 当前位是0,那么就把ans的当前位改为1
                ans |= nn;
            }
            nn <<= 1;
        }

        return ans;
    }

    // 方法二 一次异或
    public int findComplement2(int num) {

        if (num == 0) {
            return 1;
        }

        int n = 1;
        // 找到最高位bit
        for (int i = 0; i <= 31; i++) {
            if ((num - n) < 0) {
                // 找到了最高位
                n = i - 1;
                break;
            }
            n <<= 1;
        }

        // 最高位是n
        // 与 n个111111异或即可

        int i = 1;
        // <= n 多来一次
        for (int j = 0; j <= n; j++) {
            i <<= 1;
        }
        // 将n从10000变为1111
        i -= 1;

        return i ^ num;
    }

    public static void main(String[] args) {
        No476数字的补数 n = new No476数字的补数();
        int result = n.findComplement2(4);
        System.out.println(result);
    }

}
